package q517_findMinMoves;

import java.util.stream.IntStream;

public class Solution {
    /*
    直接考虑两个问题
    首先不限制每次从多少台洗衣机，并且取出的衣服要送到相邻洗衣机
    那么移动的次数至少受到两个条件限制
    假设洗衣机均值是avg
    1 对于最多衣服的洗衣机 至少要移动max - avg次
    2 我们将洗衣机分为两堆 假设前面的一堆 （一共 i 个洗衣机）是A 后面的一堆是B
    至少要移动 |sumA - i * avg|次 也就是sumA - i * avg为正时 就是前面的一堆往后面的移
    反正则是B向A一堆移动
    两者中求取最大值就是答案
     */
    public int findMinMoves(int[] machines) {
        int sumClothes = IntStream.of(machines).sum();
        if (sumClothes % machines.length != 0) return -1;
        int avg = sumClothes / machines.length, maxSteps = 0;
        // 复用第一个变量 不需要重新创建变量
        sumClothes = 0;
        for (int machine : machines) {
            machine -= avg;
            sumClothes += machine;
            maxSteps = Math.max(maxSteps, Math.max(Math.abs(sumClothes), machine));
        }
        return maxSteps;
    }
}
